import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-06-03
 * Time: 23:14
 */
public class TestDemo {
    //希尔
    public static void shell(int[] array,int gap){
        for(int i = gap;i<array.length;++i){
            int tmp = array[i];
            int j = i-gap;
            for(;j>=0;j-=gap){
                if(array[j]>tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    //希尔排序
    public static void shellSort(int[] array){
         int gap = array.length;
         while(gap > 1){
             shell(array,gap);
             gap /= 2;
         }
         shell(array,1);
    }
    //插入排序
    public static void insertSort(int[] array){
        for(int i =1;i<array.length;++i){
            int tmp = array[i];
            int j =i-1;
            for(;j>=0;--j){
                if(array[j]>tmp){
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    //交换元素
    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //选择排序
    public static void selectSort(int[] array){
         for(int i =0;i<array.length;++i){
             int minIndex =i;
             for(int j = i+1;j<array.length;j++){
                 if(array[j]<array[minIndex]){
                     minIndex = j;
                 }
             }
             swap(array,minIndex,i);
         }
    }

    public static void main(String[] args) {
        //希尔排序
        int[] array1 = {9,1,2,5,7,4,8,6,3,5,0};
        insertSort(array1);
        System.out.println(Arrays.toString(array1));
        int[] array = {9,1,2,5,7,4,8,6,3,5,0};
//        shellSort(array);
//
        selectSort(array);
        System.out.println(Arrays.toString(array));

    }

}



